洛谷题解 P1821 【[USACO07FEB]银牛派对Silver Cow Party】

发表于 | 阅读次数：
本文字数： 1.7k | 阅读时长 ≈ 2 分钟

[USACO07FEB]银牛派对Silver Cow Party

题意：

有$n$头牛，$m$条路，所有牛要前往$X$牛的家开趴（当然$X$牛不用动），求其他牛去开趴来回的最短距离，输出最长的那条。

简化版题意：

有$n$个节点，$m$条边，给出终点$X$，求其他节点到终点的来回最短距离，输出最长的距离。

注意：该题所给的边为有向边，别瞎*2输出

使用的算法：SPFA

思路：

题目要找其他点到终点$X$的最短路径和终点$X$到其他点的最短路径。为便于代码实现，要进行反向建图，用SPFA跑正向的图求终点$X$到其他点的最短路径，再用跑反向图求其他点到终点$X$的最短路径。

反向图即将边的起点和终点反过来，边权不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
struct edge
{
	int u,v;	
};

vector<edge> G[3][1001];//动态数组存边

queue<int> Q;//队列（STL大法好）

int n,m,f[3][1001],l,ans;
bool vis[1001];

void spfa(int k)//k=1时正向图，k=2时反向图
{
	memset(vis,0,sizeof(vis));//初始化false
	vis[l]=true;
	f[k][l]=0;
	Q.push(l);
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[k][news].size();i++)
		{
			int v=G[k][news][i].v,u=G[k][news][i].u;
			if(f[k][v]>f[k][news]+u)
			{
				f[k][v]=f[k][news]+u;
				if(!vis[v])
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&l);
	memset(f,0x3f3f3f,sizeof(f));
	for(int a=1;a<=m;a++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		edge cmp;
		cmp.v=y;
		cmp.u=z;
		G[1][x].push_back(cmp);//正向建图
		cmp.v=x;
		G[2][y].push_back(cmp);//反向建图
	}
	spfa(1);//跑正向图
	spfa(2);//跑反向图
	for(int a=1;a<=n;a++)
	{
		if(a==l)
		{
			continue;
		}
		ans=max(f[1][a]+f[2][a],ans);//找最长的
	}
	printf("%d\n",ans);
	return 0;
}

题目详见:https://www.luogu.org/problemnew/show/P1821